/**
 * 给定正整数 n，找到若干个完全平方数使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
 * 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
 **/
#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
using namespace std;

/**
 * Solution 1:动态规划 
 * 完全背包问题，完全平方数相当于物品，总和n相当于背包
 * 对于和i，dp[i] = min(dp[i], dp[i-j*j]+1)
 * dp[i-j*j]+1表示i减去小于它的平方和对应的数的组合数
 **/
class Solution_1 {
public:
    int numSquares(int n) {
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j*j<=i; j++){
                // 真正有比较价值的是减去不同平方数时的求解结果
                // 为了能用min函数直接取最小，要把dp初始化成INT_MAX，这样才能避免dp[i]对结果的错误影响
                dp[i] = min(dp[i], dp[i-j*j] + 1);
            }
        }
        return dp[n];
    }
};


/**
 * Solution 2:BFS广度优先
 * 转换成搜索树最短路径问题
 * 例：         12
 *          /   |   \
 *         3    8    11
 *        /   / \  / | \
 *       2   4  7 2  7  10
 *      /   / \ | | | \ | \
 *     1   0  ……  ……  ……  ……
 *    /
 *   0
 * 每一个数依此减去比它小的平方数，直到得到0。
 * 过程可写成一棵数，根节点为n，叶节点为0，非叶节点为n减去完全平方数后的差值。
 * 求最少完全平方数等同于求根节点到叶节点的最短路径。
 * 广度优先，按层搜索，搜索到第一个0的层数就是最短路径。
 **/
class Solution {
public:
    int numSquares(int n) {
        // 用队列实现BFS
        queue<int> Q;
        Q.push(n);
        // set记录节点
        // set<int> visited;

        int step = 1;

        // 当队列不为空时
        while (Q.size())
        {
            int current_len = Q.size();
            while (current_len --)
            {
                // 获取队列第一个元素
                int tmp = Q.front();
                Q.pop();
                // 对每一个tmp，计算其减去不超过它的完全平方数的差值
                for(int i=1; i*i<=tmp; i++){
                    int res = tmp - i * i;
                    // 如果差值为0，说明到达叶子节点，返回当前树的层数
                    if(res == 0){
                        return step;
                    }
                    // 剩余数不为0，加入队列，继续进行上面的操作
                    Q.push(res);
                }
            }
            // 一层遍历结束，层数加1，开始遍历下一层
            step ++;
        }
    return 0;  
    }
};

int main(){
    int n = 14;
    Solution s;
    int result = s.numSquares(n);
    cout<<result;
}